﻿using System;
namespace Graphs
{
    public class TwoColor
    {
        private bool[] marked;
        private bool[] color;
        private bool isTwoColorable = true;

        public TwoColor(Graph G)
        {
            marked = new bool[G.V()];
            color = new bool[G.V()];
            for(var s = 0;s<G.V();s++)
            {
                if (!marked[s])
                    Dfs(G,s);
            }
        }

        private void Dfs(Graph g, int v)
        {
            marked[v] = true;
            foreach (var w in g.Adj(v))
            {
                if (!marked[w])
                {
                    color[w] = !color[v];
                    Dfs(g, w);
                }
                else if (color[w] == color[v])
                    isTwoColorable = false;
            }
        }

        public bool IsBipartite()
        {
            return isTwoColorable;
        }
    }
}
